`
https://leetcode.cn/problems/clone-graph/
`

/**
 * // Definition for a _Node.
 * function _Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {_Node} node
 * @return {_Node}
 */
var cloneGraph = function (node) {
  // 记录 DFS 已经遍历过的结点
  const visited = new Set()
  // 记录原节点到克隆节点的映射
  const toClone = new Map()

  const traverse = (node) => {
    if (node === null) {
      return
    }

    if (visited.has(node)) {
      return
    }

    // 前序位置
    // 标记本结点为已访问
    visited.add(node)

    // 如果本结点还没克隆过， 克隆结点
    if (!toClone.has(node)) {
      toClone.set(node, new _Node(node.val))
    }
    // 克隆结点
    const cloneNode = toClone.get(node)

    // 遍历所有结点
    for (const neighbor of node.neighbors) {
      traverse(neighbor)
      // 后序位置
      // 递归之后，相邻结点一定已创建好
      const cloneNeighbor = toClone.get(neighbor)
      cloneNode.neighbors.push(cloneNeighbor)
    }
  }

  traverse(node)

  return toClone.get(node)
};